package 中等.滑动窗口;

import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子
 * 数组。删除子数组的 得分 就是子数组各元素之 和 。
 * 返回 只删除一个 子数组可获得的 最大得分 。
 * 如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],
 * a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-erasure-value
 */
public class 删除子数组的最大得分_1695 {

    public static void main(String[] args) {

        System.out.println(maximumUniqueSubarray(new int[]{4, 2, 4, 5, 6}));

    }

    /**
     * 滑动窗口+哈希表
     * 窗口中只能包含不重复的数字
     *
     * @param nums
     * @return
     */
    public static int maximumUniqueSubarray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 0, sum = 0;
        int left = 0, right = 0;

        while (right < nums.length) {
            // nums[right] 没有加到 sum 中，[left,right-1] 的和
            while (right < nums.length && set.add(nums[right])) {
                sum += nums[right];
                right++;
            }
            max = Math.max(max, sum);

            // 找到左边和 nums[right] 重复的元素
            while (right < nums.length && nums[left] != nums[right]) {
                sum -= nums[left];
                set.remove(nums[left]);
                left++;
            }
            // 排除掉左边重复的元素，sum 和没变，用nums[right]代替
            left++;
            right++;
        }

        return max;
    }

}
